CF1267L Lexicography

需要一点点思维的基础构造题

题解：

首先贪心并且显然的，字符是要从小到大确定各自位置的

其次，在确定单词时我们只需要可以确定前k个，其余的不用管，且要在合法的前提下，使得串k的各位最小

考虑字典序，发现只要高位小就可以无视低位是啥，因此我们可以在确定前面的串一定会小于k后就将它们“无视”掉，从而将原本应该分配给他们的较小字符分给k，而“无视掉”的串的低位由于对k没有影响（反正高位已经小于了），就可以按顺序插较大字符了

因此对于从高到低的每一位都是从k-1到1，倒着扫一遍哪些是“有可能”大于等于k的，刻意插小字符就好了（另外，显然的，这个“有可能”的区间一定是连贯的呢）

照着数据手玩几组应该就可以很快搞懂下面的代码：

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=1005;
char s[N*N],ans[N][N];
int n,l,k,use;

signed main(){
    read(n);read(l);read(k);;
    scanf("%s",s+1);
    sort(s+1,s+1+n*l); //贪心的排个序
    for(int i=1;i<=l;i++){
        int pos=k; //区间[pos,k-1]都是有可能大于等于k的串，因此要特意插小字符把他们扼杀掉
        while(pos>=2&&ans[pos-1][i-1]==ans[k][i-1]) pos--;
        for(int j=pos;j<=k;j++) ans[j][i]=s[++use]; //按顺序插小字符
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=l;j++) if(ans[i][j]=='\0') //这个位置上没有字符
            ans[i][j]=s[++use];
    for(int i=1;i<=n;i++) printf("%s\n",ans[i]+1);
}